#pragma once

//C++ Hand File
#include <iostream>
#include "reverse_iterator.h"
using std::pair;
using std::make_pair;
using std::cout;
using std::endl;
using std::less;
using std::greater;

//C Hand File
#include <cassert>

enum Color //红黑树颜色标记
{
	RED, //红色
	BLACK, //黑色
};

namespace my_rb_tree
{
	template<class T>
	struct RBTreeNode
	{
		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		RBTreeNode<T>* _parent;
		T _data;
		Color _col;

		RBTreeNode(const T& data)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _data(data)
			, _col(RED) //新节点默认红色
		{}

		RBTreeNode(const T& data, const Color& c)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _data(data)
			, _col(c) //新节点默认红色
		{}
	};


	template<class T, class Ref, class Ptr>
	struct __RBTreeIterator
	{
		typedef __RBTreeIterator<T, T&, T*> iterator;
		typedef __RBTreeIterator<T, Ref, Ptr> self;
		typedef RBTreeNode<T> Node;
		Node* _node;

		__RBTreeIterator(Node* node)
			:_node(node)
		{}

		//__RBTreeIterator(const self& s)
		//	:_node(s._node)
		//{}

		//普通迭代器下该函数相当于拷贝构造
		//const迭代器时相当于类型转换 通过普通迭代器构造const迭代器
		__RBTreeIterator(const iterator& it)
			:_node(it._node)
		{}
		//因为set需要防止key被随意修改破坏树结构，将普通迭代器和const迭代器都设置为const迭代器，但是普通迭代器与const迭代器无法进行类型转换
		//当迭代器为普通迭代器时该函数替代拷贝构造
		//当迭代器为const迭代器时，该函数为可以将普通迭代器构造为const迭代器的转换函数，而const迭代器的拷贝构造使用默认的即可

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_node->_data);
		}

		bool operator==(const self& it) const
		{
			return _node == it._node;
		}

		bool operator!=(const self& it) const
		{
			return _node != it._node;
		}

		self& operator++()
		{
			Increament(); //节点走向下一个节点
			return *this;
		}

		self operator++(int)
		{
			self tmp = *this;
			Increament(); //节点走向下一个节点
			return tmp;
		}

		self& operator--()
		{
			DeIncreament(); //节点走向下一个节点
			return *this;
		}

		self operator--(int)
		{
			self tmp = *this;
			DeIncreament(); //节点走向下一个节点
			return tmp;
		}

	private:
		void Increament() //++从左向右遍历
		{
			if (_node->_right) //判断右子树是否存在 存在则访问右节点的左子树
			{
				Node* cur = _node->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				_node = cur;
			}
			else //右子树访问完毕，访问祖父节点
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent && parent->_right == cur) //一直遍历到最开始左节点的位置 前往祖父节点
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
		}

		void DeIncreament() //--从右向左遍历
		{
			if (_node && _node->_left)
			{
				Node* cur = _node->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_node = cur;
			}
			else
			{
				Node* cur = _node;
				Node* parent = cur->_parent;
				while (parent && parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
		}
	};

	template<class Iterator, class Ref, class Ptr>
	struct __RBTree_Reverse_Iterator
	{
		Iterator current; //构造正向迭代器对象

		typedef __RBTree_Reverse_Iterator<Iterator, Ref, Ptr> self;

		__RBTree_Reverse_Iterator(Iterator it) //普通迭代器构造
			:current(it)
		{}

		__RBTree_Reverse_Iterator(const self& s) //拷贝构造
			:current(s.current)
		{}

		self& operator++()
		{
			--current;
			return *this;
		}

		self operator++(int)
		{
			self tmp = current;
			--current;
			return tmp;
		}

		self& operator--()
		{
			++current;
			return *this;
		}

		self operator--(int)
		{
			self tmp = current;
			++current;
			return tmp;
		}

		bool operator==(const self& s)
		{
			return current == s.current;
		}

		bool operator!=(const self& s)
		{
			return current != s.current;
		}

		Ref operator*()
		{
			return *current;
		}

		Ptr operator->()
		{
			return &(operator*());
		}

	};

	template<class K, class T,class Compare,class KeyOfValue>
	class RBTree
	{
		typedef RBTreeNode<T> Node;

		//迭代器部分
	public:
		typedef __RBTreeIterator<T, T&, T*> iterator;
		typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
		typedef __RBTree_Reverse_Iterator<iterator, T&, T*> reverse_iterator;
		typedef __RBTree_Reverse_Iterator<const_iterator,const T&,const T*> const_reverse_iterator;

		iterator begin()
		{
			Node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return iterator(cur);
		}
		iterator end() { return iterator(nullptr); }

		const_iterator begin() const
		{
			Node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return const_iterator(cur);
		}
		const_iterator end() const { return const_iterator(nullptr); }

		const_iterator cbegin() const
		{
			Node* cur = _root;
			while (cur && cur->_left)
			{
				cur = cur->_left;
			}
			return const_iterator(cur);
		}
		const_iterator cend() const { return const_iterator(nullptr); }

		reverse_iterator rend() { return reverse_iterator(iterator(nullptr)); }
		reverse_iterator rbegin()
		{
			Node* cur = _root;
			while (cur && cur->_right)
			{
				cur = cur->_right;
			}
			return reverse_iterator(iterator(cur));
		}

		const_reverse_iterator rbegin() const 
		{
			Node* cur = _root;
			while (cur && cur->_right)
			{
				cur = cur->_right;
			}
			return const_reverse_iterator(const_iterator(cur));
		}
		const_reverse_iterator rend() const { return const_reverse_iterator(const_iterator(nullptr)); }


		const_reverse_iterator crbegin() const 
		{
			Node* cur = _root;
			while (cur && cur->_right)
			{
				cur = cur->_right;
			}
			return const_reverse_iterator(const_iterator(cur));
		}
		const_reverse_iterator crend() const { return const_reverse_iterator(const_iterator(nullptr)); }


		//功能函数部分
	public:
		RBTree()
			:_root(nullptr)
			,nodenum(0)
		{}

		RBTree(const RBTree<K, T,Compare,KeyOfValue>& rbt)
			:_root(nullptr)
			,nodenum(rbt.nodenum)
		{
			_root = copy(rbt._root);
		}

		size_t size() const
		{
			return nodenum;
		}

		bool empty() const
		{
			return nodenum == 0; //空为真
		}

		void clear() const 
		{
			Destroy(_root);
			_root = nullptr;
			nodenum = 0;
		}

		void swap(RBTree<K, T, Compare, KeyOfValue>& rbt)
		{
			Node* tmp = _root;
			_root = rbt._root;
			rbt._root = tmp;
		}

		void operator=(const RBTree<K, T, Compare, KeyOfValue>& rbt)
		{
			RBTree<K, T, Compare, KeyOfValue> tmp = rbt;
			swap(tmp);
		}

		pair<iterator,bool> Insert(const T& data)
		{

			if (!_root) //无节点 直接插入 根节点为黑
			{
				_root = new Node(data);
				_root->_col = BLACK;
				++nodenum;
				return make_pair(_root,true);
			}

			Node* parent = _root;
			Node* cur = _root;
			while (cur)
			{
				//if (cur->_data.first > data.first) //当前节点>插入值(升序)
				if(_com(_kov(data),_kov(cur->_data)))
				{
					parent = cur;
					cur = cur->_left;
				}
				//else if (cur->_data.first < data.first) //当前节点<插入值(升序)
				else if(_com(_kov(cur->_data), _kov(data)))
				{
					parent = cur;
					cur = cur->_right;
				}
				else //相同 返回false
				{
					return make_pair(cur, false);
				}
			}

			cur = new Node(data);
			Node* newnode = cur;
			//if (parent->_data.first > cur->_data.first) //判断新节点应该插在左边还是右边(升序)
			if(_com(_kov(cur->_data),_kov(parent->_data)))
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;

			//开始调整
			while (parent && parent->_col == RED) //两个红色则需要调整
			{
				Node* grandfather = parent->_parent;
				//判断祖父的左右找叔叔
				if (grandfather->_left == parent) //父节点是祖父的左
				{
					Node* uncle = grandfather->_right;//叔叔是祖父的右
					if (uncle && uncle->_col == RED) //叔叔存在且为红
					{
						parent->_col = BLACK; //父亲和叔叔变黑
						uncle->_col = BLACK;
						grandfather->_col = RED; //祖父变红

						cur = grandfather; //更新节点 继续检测
						parent = cur->_parent;
					}
					else //叔叔不存在或叔叔为黑
					{
						if (cur == parent->_left) //cur是parent的左 - 右旋 - 左左
						{
							//     g
							//    p u
							//   c
							RotateR(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else //cur是parent的右边 - 双旋 - 左右旋
						{
							//     g          g         
							//   p   u ->   p   u
							//    c       c    
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
							parent->_col = RED;
						}
						break; //调整完可以跳出
					}
				}
				else
				{
					Node* uncle = grandfather->_left;//叔叔是祖父的左
					if (uncle && uncle->_col == RED) //叔叔存在且为红
					{
						parent->_col = BLACK; //父亲和叔叔变黑
						uncle->_col = BLACK;
						grandfather->_col = RED; //祖父变红

						cur = grandfather; //更新节点 继续检测
						parent = cur->_parent;
					}
					else //叔叔不存在或叔叔为黑
					{
						if (cur == parent->_right) //cur是父亲的右边 - 左旋 - 右右
						{ //变色形式与左左一样
						//     g
						//   u   p
						//         c
							RotateL(grandfather);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else
						{
							//     g
							//   u   p
							//      c
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
							parent->_col = RED;
						}
						break; //调整完可以跳出
					}
				}
			}

			_root->_col = BLACK; //根节点始终为黑
			++nodenum;
			return make_pair(newnode, true);
		}

		void midorder() const //中序遍历
		{
			_midorder(_root);
		}

		bool IsBalanceTree()
		{
			int leftblack = 0;
			int rightblack = 0;

			Node* cur = _root;
			while (cur)
			{
				if (cur->_col == BLACK)
					++leftblack;

				cur = cur->_left;
			}
			cur = _root;
			while (cur)
			{
				if (cur->_col == BLACK)
					++rightblack;

				cur = cur->_right;
			}
			if (leftblack == rightblack)
				return _Check(_root, 0, leftblack);

			return false;

		}

		iterator Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (_kov(cur->_data) > key)
					cur = cur->_left;
				else if (_kov(cur->_data) < key)
					cur = cur->_right;
				else
					return iterator(cur);
			}
			return iterator(nullptr);
		}

		~RBTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

	private:
		void Destroy(Node* root)
		{
			if (!root) return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
			nodenum = 0;
		}

		void RotateL(Node* parent) //左单旋
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;

			if (subRL) //如果subR的左孩子存在
				subRL->_parent = parent;

			parent->_right = subRL;
			subR->_left = parent;

			Node* grandfather = parent->_parent;
			if (grandfather) //是子树 调整parent的父节点指向
			{
				if (grandfather->_left == parent)
				{
					grandfather->_left = subR;
				}
				else
				{
					grandfather->_right = subR;
				}
				subR->_parent = grandfather;
			}
			else //是根节点
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			parent->_parent = subR;
		}

		void RotateR(Node* parent) //右单旋
		{
			Node* subL = parent->_left;
			Node* subLR = subL->_right;

			if (subLR)
				subLR->_parent = parent;

			parent->_left = subLR;
			subL->_right = parent;

			Node* grandfather = parent->_parent;
			if (grandfather)
			{
				if (grandfather->_left == parent)
				{
					grandfather->_left = subL;
				}
				else
				{
					grandfather->_right = subL;
				}
				subL->_parent = grandfather;
			}
			else
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			parent->_parent = subL;
		}

		void _midorder(Node* root) //中序遍历子函数
		{
			if (!root) return;
			_midorder(root->_left);
			cout << root->_data.first << ":" << root->_data.second << endl;
			_midorder(root->_right);
		}

		bool _Check(Node* root, int NodeNum, int BlackNum)
		{
			if (!root)
			{
				//cout << NodeNum << endl; //打印黑色节点数
				if (NodeNum == BlackNum)
					return true;
				else
					return false;
			}

			if (root->_col == BLACK) //黑色节点就++
				++NodeNum;

			if (root->_col == RED && root->_parent && root->_parent->_col == RED) //不能出现两个连续的红色节点
			{
				cout << "出现两个连续的红色节点：" << root->_parent->_data.first << "和" << root->_data.first << endl;
				return false;
			}

			return _Check(root->_left, NodeNum, BlackNum) && _Check(root->_right, NodeNum, BlackNum);
		}

		Node* copy(Node* root)
		{
			if (!root) return nullptr;

			Node* newnode = new Node(root->_data, root->_col);

			newnode->_left = copy(root->_left);
			if (newnode->_left)
				newnode->_left->_parent = newnode;
			newnode->_right = copy(root->_right);
			if (newnode->_right)
				newnode->_right->_parent = newnode;

			return newnode;
		}

		Node* _root;
		Compare _com;
		KeyOfValue _kov;
		size_t nodenum;
	};

}

